package com.agile.leetcode.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * hash+双向链表实现lru最近最少使用算法
 *
 * @Author ChenZhangKun
 * @Date 2020/12/28 9:31
 */
public class LRUCache {
    public static void main(String[] args) {
        LRUCache cache=new LRUCache(2);
        cache.put(1,2);
        cache.put(2,3);
        cache.put(3,4);
        cache.put(4,5);
        System.out.println(cache);
    }
    class DoubleLinkNode{
        // 键
        private int key;
        // 值
        private int value;
        // 上一个
        private DoubleLinkNode pre;
        // 下一个
        private DoubleLinkNode next;

        public DoubleLinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public DoubleLinkNode() {
        }

        @Override
        public String toString() {
            return "DoubleLinkNode{" +
                    "key=" + key +
                    ", value=" + value +
                    ", pre=" + pre +
                    ", next=" + next +
                    '}';
        }
    }
    // hash
    private Map<Integer,DoubleLinkNode> map=new HashMap<>(16);
    // 头指针
    private DoubleLinkNode head;
    // 尾指针
    private DoubleLinkNode tail;
    // 容量
    private int capacity;
    // 长度
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size=0;
        this.head=new DoubleLinkNode();
        this.tail=new DoubleLinkNode();
    }

    /**
     * 拿到node
     * @param key
     * @return
     */
    public int get(int key){
        // 缓存中取
        DoubleLinkNode doubleLinkNode = map.get(key);
        if (doubleLinkNode!=null){
            // 添加至头部
            this.moveToHead(doubleLinkNode);
            return doubleLinkNode.value;
        }
        return -1;
    }

    /**
     * 添加到头部方法
     * @param doubleLinkNode
     */
    private void moveToHead(DoubleLinkNode doubleLinkNode) {
        this.remove(doubleLinkNode);
        // 移动到头部
        this.addToHead(doubleLinkNode);
    }

    /**
     * 添加到头部
     * @param doubleLinkNode
     */
    private void addToHead(DoubleLinkNode doubleLinkNode) {
        if (head.next==null){
            head.next=doubleLinkNode;
            doubleLinkNode.pre=head;
            if (tail.pre==null){
                tail.pre=doubleLinkNode;
                doubleLinkNode.next=tail;
            }
            return;
        }
        DoubleLinkNode next = head.next;
        doubleLinkNode.next=next;
        next.pre=doubleLinkNode;
        head.next=doubleLinkNode;
        doubleLinkNode.pre=head;
    }

    /**
     * 删除该节点
     * @param doubleLinkNode
     */
    private void remove(DoubleLinkNode doubleLinkNode) {
        doubleLinkNode.pre.next=doubleLinkNode.next;
        doubleLinkNode.next.pre=doubleLinkNode.pre;
    }
    public void put(int key,int value){
        // 缓存中有没有
        DoubleLinkNode doubleLinkNode = map.get(key);
        // 缓存中没有
        if (doubleLinkNode==null){
            DoubleLinkNode newNode=new DoubleLinkNode(key,value);
            // 缓存满了没有
            if (size==this.capacity){
                // 缓存满，淘汰末尾
                int oldKey=removeTail();
                // 删除map缓存
                map.remove(oldKey);
                // 添加到头部
                addToHead(newNode);
                // 添加到hash表
                map.put(key,newNode);
            }else {
                // 添加到头部
                addToHead(newNode);
                map.put(key,newNode);
                size++;
            }
        }else {
            // 替换值
            doubleLinkNode.value=value;
            // 删除原来的并添加到头部
            this.moveToHead(doubleLinkNode);
        }
    }

    private int removeTail() {
        DoubleLinkNode doubleLinkNode=tail.pre;
        remove(doubleLinkNode);
        return doubleLinkNode.key;
    }
}
